class Solution {
    /*
        代码：root.left = pre; 可以修改的原因是 dfs(root.left);
            即左边的树已经遍历了
        同理，对于“pre.right = root;” ,pre表示已经遍历过的节点，
            当然可以遍历了
     */
    Node head,pre;
    public Node treeToDoublyList(Node root) {
        if(root==null)
            return null;
        dfs(root);
        head.left = pre;  // 连接头尾节点
        pre.right = head;
        return head;
    }
    public void dfs(Node root) {
        if (root == null)
            return;
        dfs(root.left);
        if (pre == null) // 第一个遍历的节点是 值最小的节点
            head = root;
        else
            pre.right = root;
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}